% this file is called up by thesis.tex
% content in this file will be fed into the main document

%: ----------------------- name of chapter  -------------------------
\chapter{Conclusion} % top level followed by section, subsection
\label{chapter:conclusion}

%: ----------------------- contents from here ------------------------
In this dissertation, we have developed and analyzed positive
diffusion processes under both organic dynamics and adversarial
dynamics. We have also designed and analyzed intervention strategies
to control negative diffusion. We now conclude by summarizing our
results and by presenting a few directions for future research.

\section{Enable positive diffusion}
In the first half of the dissertation, we considered the question of
how to design efficient algorithms to enable positive diffusion. 
\begin{itemize}
\item We first looked at diffusion under organic dynamics, where the
  communication network is altered by diffusion itself. We proposed
  two natural and simple processes, triangulation and two-hop
  walk. These two processes are good algorithms to solve resource
  discovery, group member discovery, and lots of other problems. We
  have shown in undirected graphs both processes complete in
  $O(n\log^2 n)$ rounds, and proved an $\Omega(n\log n)$ lower
  bound. This is an almost tight bound with a logarithmic gap. We also
  proved that in directed graphs, two-hop walk process completes in
  $O(n^2\log n)$ rounds, and gave a matching lower bound
  $\Omega(n^2\log n)$ in weakly connected directed graphs, and lower
  bound $\Omega(n^2)$ in strongly connected directed graphs.
\item We then looked at diffusion under adversarial dynamics, more
  specifically, $k$-gossip problem. There we adopted the online
  adversary model proposed in \cite{kuhn+lo:dynamic}, where Kuhn et al
  showed an $O(kn)$ upper bound and an $\Omega(n\log k)$ lower
  bound. We improve their lower bound to $\Omega(kn/\log n)$, which is
  an almost tight bound. This suggests that under the adversarial
  model defined in \cite{kuhn+lo:dynamic}, we cannot have efficient
  token-forwarding based algorithms. Thus, we designed an
  $O(n\sqrt{k\log n})$ algorithm and an bicriteria $(O(n^\epsilon),
  \log n)$ approximation algorithm under offline adversarial model,
  where the adversary has to give the whole sequence of communication
  graphs up in front.
\end{itemize}

\section{Control negative diffusion}
In the second half of this dissertation, we switch gear to ask the
question of how to control negative diffusion.
\begin{itemize}
\item We first designed an $O(\log n)$ approximation algorithm for the
  optimal centralized intervention strategy, where the algorithm picks
  a set of nodes in the network to apply interventions in order to
  minimize the cost of negative diffusion.
\item We then looked at the setting where nodes in the network make
  their own decision if they want to secure themselves. We used game
  theory to show the existence and non-existence of Nash
  equilibrium. We also compare the cost of decentralized solution with
  the optimal centralized solution, in other word, price of anarchy.
\item Last, we analyze negative diffusion in the presence of risk
  behavior changes. We have observed and analyzed two counter
  intuitive phenomena: 1) less interventions can be more effective,
  and 2) targeted intervention strategy can be worse than random
  intervention strategy.
\end{itemize}

% ---------------------------------------------------------------------------
%: ----------------------- end of thesis sub-document ------------------------
% ---------------------------------------------------------------------------

